package teach.sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 1, 4, 9, 0, 3, 5, 2, 7, 6};
        //int[] arr = {6, 4, 9, 1, 7, 2, 5, 8};
        System.out.println(Arrays.toString(arr));
        arr = sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static int[] sort(int[] arr,int start,int end){
        if(start==end){
            return new int[]{arr[start]};
        }

        int mid = start + (end-start)/2;
        int[] leftArr = sort(arr,start,mid);
        int[] rightArr = sort(arr,mid+1,end);
        int l = 0;
        int r = 0;

        int[] newArr = new int[leftArr.length+rightArr.length];
        int n = 0;

        while(l<leftArr.length && r<rightArr.length){
            newArr[n++] = leftArr[l]<=rightArr[r] ? leftArr[l++] : rightArr[r++];
            /*if(leftArr[l]<=rightArr[r]){
                newArr[n] = leftArr[l++];
            }else{
                newArr[n] = rightArr[r++];
            }
            n++;*/
        }
        while(r< rightArr.length){
            newArr[n++] = rightArr[r++];
        }
        while(l< leftArr.length){
            newArr[n++] = leftArr[l++];
        }
        return newArr;
    }
}
